package org.example.leetcode;

/**
 * @Author: tongqianwen
 * @Date: 2025/2/11
 */
public class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==1){
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i <n ; i++) {
            dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[n-1];
    }

    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2] );

        }
        return dp[n];
    }


    public int tribonacci(int n) {
        int[] tri = new int[]{0,1,1};
        for (int i = 3; i <=n ; i++) {
            tri[i%3] = tri[0]+tri[1]+tri[2];
        }
        return tri[n%3];
    }

    public int fib(int n) {
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }
        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] =1;
        for (int i = 2; i <=n; i++) {
            int sum = dp[0]+dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }


    public int climbStairs(int step) {

        if(step < 1 || step > 45){
            throw new RuntimeException("error param: "+ step);
        }
        if(step<=1){
            return step;
        }
        int[] dp = new int[step+1];
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <= step; i++) {
            dp[i] = dp[i-1]+dp[i-2];
        }

        return dp[step];
    }

    public static void main(String[] args) {
        System.out.println("Hello world!");
        Solution solution = new Solution();
        System.out.println(solution.minCostClimbingStairs(new int[]{1,1,2,1,3,1,4}));
        System.out.println(solution.tribonacci(4));
        System.out.println(solution.tribonacci(3));
        System.out.println(solution.tribonacci(2));
        System.out.println(solution.fib(2));
        System.out.println(solution.fib(3));
        System.out.println(solution.climbStairs(45));
    }
}
